package java_cup;

import java.util.Hashtable;
import java.util.Enumeration;

/**
 * This class represents a set of LALR items. For purposes of building these
 * sets, items are considered unique only if they have unique cores (i.e.,
 * ignoring differences in their lookahead sets).
 * <p>
 * 
 * This class provides fairly conventional set oriented operations (union,
 * sub/super-set tests, etc.), as well as an LALR "closure" operation (see
 * compute_closure()).
 * 
 * @see java_cup.lalr_item
 * @see java_cup.lalr_state
 * @version last updated: 3/6/96
 * @author Scott Hudson
 */

public class lalr_item_set {

	/*-----------------------------------------------------------*/
	/*--- Constructor(s) ----------------------------------------*/
	/*-----------------------------------------------------------*/

	/** Constructor for an empty set. */
	public lalr_item_set() {
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Constructor for cloning from another set.
	 * 
	 * @param other
	 *            indicates set we should copy from.
	 */
	public lalr_item_set(lalr_item_set other) throws internal_error {
		not_null(other);
		_all = (Hashtable) other._all.clone();
	}

	/*-----------------------------------------------------------*/
	/*--- (Access to) Instance Variables ------------------------*/
	/*-----------------------------------------------------------*/

	/**
	 * A hash table to implement the set. We store the items using themselves as
	 * keys.
	 */
	protected Hashtable _all = new Hashtable(11);

	/** Access to all elements of the set. */
	public Enumeration all() {
		return _all.elements();
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Cached hashcode for this set. */
	protected Integer hashcode_cache = null;

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Size of the set */
	public int size() {
		return _all.size();
	}

	/*-----------------------------------------------------------*/
	/*--- Set Operation Methods ---------------------------------*/
	/*-----------------------------------------------------------*/

	/**
	 * Does the set contain a particular item?
	 * 
	 * @param itm
	 *            the item in question.
	 */
	public boolean contains(lalr_item itm) {
		return _all.containsKey(itm);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Return the item in the set matching a particular item (or null if not
	 * found)
	 * 
	 * @param itm
	 *            the item we are looking for.
	 */
	public lalr_item find(lalr_item itm) {
		return (lalr_item) _all.get(itm);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Is this set an (improper) subset of another?
	 * 
	 * @param other
	 *            the other set in question.
	 */
	public boolean is_subset_of(lalr_item_set other) throws internal_error {
		not_null(other);

		/* walk down our set and make sure every element is in the other */
		for (Enumeration e = all(); e.hasMoreElements();)
			if (!other.contains((lalr_item) e.nextElement()))
				return false;

		/* they were all there */
		return true;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Is this set an (improper) superset of another?
	 * 
	 * @param other
	 *            the other set in question.
	 */
	public boolean is_superset_of(lalr_item_set other) throws internal_error {
		not_null(other);
		return other.is_subset_of(this);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Add a singleton item, merging lookahead sets if the item is already part
	 * of the set. returns the element of the set that was added or merged into.
	 * 
	 * @param itm
	 *            the item being added.
	 */
	public lalr_item add(lalr_item itm) throws internal_error {
		lalr_item other;

		not_null(itm);

		/* see if an item with a matching core is already there */
		other = (lalr_item) _all.get(itm);

		/* if so, merge this lookahead into the original and leave it */
		if (other != null) {
			other.lookahead().add(itm.lookahead());
			return other;
		}
		/* otherwise we just go in the set */
		else {
			/* invalidate cached hashcode */
			hashcode_cache = null;

			_all.put(itm, itm);
			return itm;
		}
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Remove a single item if it is in the set.
	 * 
	 * @param itm
	 *            the item to remove.
	 */
	public void remove(lalr_item itm) throws internal_error {
		not_null(itm);

		/* invalidate cached hashcode */
		hashcode_cache = null;

		/* remove it from hash table implementing set */
		_all.remove(itm);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Add a complete set, merging lookaheads where items are already in the set
	 * 
	 * @param other
	 *            the set to be added.
	 */
	public void add(lalr_item_set other) throws internal_error {
		not_null(other);

		/* walk down the other set and do the adds individually */
		for (Enumeration e = other.all(); e.hasMoreElements();)
			add((lalr_item) e.nextElement());
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Remove (set subtract) a complete set.
	 * 
	 * @param other
	 *            the set to remove.
	 */
	public void remove(lalr_item_set other) throws internal_error {
		not_null(other);

		/* walk down the other set and do the removes individually */
		for (Enumeration e = other.all(); e.hasMoreElements();)
			remove((lalr_item) e.nextElement());
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Remove and return one item from the set (done in hash order). */
	public lalr_item get_one() throws internal_error {
		Enumeration the_set;
		lalr_item result;

		the_set = all();
		if (the_set.hasMoreElements()) {
			result = (lalr_item) the_set.nextElement();
			remove(result);
			return result;
		} else
			return null;
	}

	/*-----------------------------------------------------------*/
	/*--- General Methods ---------------------------------------*/
	/*-----------------------------------------------------------*/

	/**
	 * Helper function for null test. Throws an interal_error exception if its
	 * parameter is null.
	 * 
	 * @param obj
	 *            the object we are testing.
	 */
	protected void not_null(Object obj) throws internal_error {
		if (obj == null)
			throw new internal_error("Null object used in set operation");
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Compute the closure of the set using the LALR closure rules. Basically
	 * for every item of the form:
	 * 
	 * <pre>
	 *    [L ::= a *N alpha, l]
	 * </pre>
	 * 
	 * (where N is a a non terminal and alpha is a string of symbols) make sure
	 * there are also items of the form:
	 * 
	 * <pre>
	 *    [N ::= *beta, first(alpha l)]
	 * </pre>
	 * 
	 * corresponding to each production of N. Items with identical cores but
	 * differing lookahead sets are merged by creating a new item with the same
	 * core and the union of the lookahead sets (the LA in LALR stands for
	 * "lookahead merged" and this is where the merger is). This routine assumes
	 * that nullability and first sets have been computed for all productions
	 * before it is called.
	 */
	public void compute_closure() throws internal_error {
		lalr_item_set consider;
		lalr_item itm, new_itm, add_itm;
		non_terminal nt;
		terminal_set new_lookaheads;
		Enumeration p;
		production prod;
		boolean need_prop;

		/* invalidate cached hashcode */
		hashcode_cache = null;

		/* each current element needs to be considered */
		consider = new lalr_item_set(this);

		/* repeat this until there is nothing else to consider */
		while (consider.size() > 0) {
			/* get one item to consider */
			itm = consider.get_one();

			/* do we have a dot before a non terminal */
			nt = itm.dot_before_nt();
			if (nt != null) {
				/* create the lookahead set based on first after dot */
				new_lookaheads = itm.calc_lookahead(itm.lookahead());

				/* are we going to need to propagate our lookahead to new item */
				need_prop = itm.lookahead_visible();

				/* create items for each production of that non term */
				for (p = nt.productions(); p.hasMoreElements();) {
					prod = (production) p.nextElement();

					/* create new item with dot at start and that lookahead */
					new_itm = new lalr_item(prod, new terminal_set(
							new_lookaheads));

					/* add/merge item into the set */
					add_itm = add(new_itm);
					/* if propagation is needed link to that item */
					if (need_prop)
						itm.add_propagate(add_itm);

					/* was this was a new item */
					if (add_itm == new_itm) {
						/* that may need further closure, consider it also */
						consider.add(new_itm);
					}
				}
			}
		}
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Equality comparison. */
	public boolean equals(lalr_item_set other) {
		if (other == null || other.size() != size())
			return false;

		/* once we know they are the same size, then improper subset does test */
		try {
			return is_subset_of(other);
		} catch (internal_error e) {
			/* can't throw error from here (because superclass doesn't) so crash */
			e.crash();
			return false;
		}

	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Generic equality comparison. */
	@Override
	public boolean equals(Object other) {
		if (!(other instanceof lalr_item_set))
			return false;
		else
			return equals((lalr_item_set) other);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Return hash code. */
	@Override
	public int hashCode() {
		int result = 0;
		Enumeration e;
		int cnt;

		/* only compute a new one if we don't have it cached */
		if (hashcode_cache == null) {
			/* hash together codes from at most first 5 elements */
			// CSA fix! we'd *like* to hash just a few elements, but
			// that means equal sets will have inequal hashcodes, which
			// we're not allowed (by contract) to do. So hash them all.
			for (e = all(), cnt = 0; e.hasMoreElements() /* && cnt<5 */; cnt++)
				result ^= ((lalr_item) e.nextElement()).hashCode();

			hashcode_cache = new Integer(result);
		}

		return hashcode_cache.intValue();
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Convert to string. */
	@Override
	public String toString() {
		StringBuffer result = new StringBuffer();

		result.append("{\n");
		for (Enumeration e = all(); e.hasMoreElements();) {
			result.append("  " + e.nextElement() + "\n");
		}
		result.append("}");

		return result.toString();
	}
	/*-----------------------------------------------------------*/
}
